﻿// 0925train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
 请帮接待员计算可以坐满车的接待方案，输出方案数量。
约束：
1. 一个团只能上一辆车，并且代表团人数（代表团数量小于30，每个代表团人数小于30）小于汽车容量（汽车容量小于100）
2. 需要将车辆坐满

输入描述
第一行代表团人数，英文逗号隔开，代表团数量小于30，每个代表团人数小于30
第二行汽车载客量，汽车容量小于100

输出描述
坐满汽车的方案数量
如果无解输出0

输入
5,4,2,3,2,4,9
10
输出
4
 */
class Solution01
{
public:
    Solution01(vector<int>&num_vec,int total)
    {
        vector<int>dynamic_v(total + 1);
        //初始化
        //凑出0，1种方案
        dynamic_v[0] = 1;

        for (auto&curr:num_vec)
        {
            for (int sum=total;sum>=0; sum--)
            {
                if (sum - curr < 0) continue;
                dynamic_v[sum] += dynamic_v[sum - curr];
            }
	        //for---
        }

        cout << dynamic_v[total];
	    //Solution01
    }
};


/*
 他发明了一种写法：给出数字个数n和行数m (0 < n < 999，0 < m < 999)
 从左上角的1开始，按照顺时针螺旋向内写方式，依次写出1, 2, 3, ..., n，最终形成一个m行矩阵
小明对这个矩阵有些要求：
1. 每行数字的个数一样多
2. 列的数量尽可能少
3. 填充数字时优先填充外部
4. 数字不够时，使用单个*号占位

输入描述
两个整数，空格隔开，依次表示n、m

输出描述
符合要求的唯一短阵

输入
9 4
输出
1 2 3
* * 4
9 * 5
8 7 6

 */
class Solution02
{
public:
    void fillNum(
        vector<vector<string>>&grid,
        int left, int right, int top, int bottom
    )
    {
        //[top][c]
        //[top][left] - [top][right]
        for (int c=left; c<=right; c++)
        {
            if (curr_num > total_) break;
            grid[top][c] = to_string(curr_num);
            curr_num++;
        }

        //[r][right]
        //[top+1][right]-[bottom][right]
        for (int r=top+1; r<=bottom; r++)
        {
            if (curr_num > total_) break;
            grid[r][right] = to_string(curr_num);
            curr_num++;
        }

        //[bottom][c]
        //[bottom][right]-[bottom][left]
        for (int c=right-1; c>=left; c--)
        {
            if (curr_num > total_) break;
            grid[bottom][c] = to_string(curr_num);
            curr_num++;
        }

        //[r][left]
        //[bottom+1][left]-[top-1][left]
        for (int r=bottom-1; r>=top+1; r--)
        {
            if (curr_num > total_) break;
            grid[r][left] = to_string(curr_num);
            curr_num++;
        }

        if (curr_num<=total_ && left+1<=right-1 && top+1<=bottom-1)
        {
            fillNum(grid, left + 1, right - 1, top + 1, bottom - 1);
        }
	    //fillNum
    }

    Solution02(int total, int row_size)
    {
        total_ = total;
        row_size_ = row_size;
        col_size_ = ceil(double(total) / double(row_size));

        vector<vector<string>>grid(row_size_, vector<string>(col_size_, "*"));

        fillNum(grid, 0, col_size_ - 1, 0, row_size_ - 1);

        for (int r = 0; r < row_size_; r++)
        {
            for (int c = 0; c < col_size_; c++)
            {
                cout << grid[r][c];
                if (c!=col_size_-1)
                {
                    cout << ' ';
                }
            }
            if (r!=row_size_-1)
            {
                cout << '\n';
            }
        }


	    //Solution02
    }
private:
    int curr_num = 1;
    int total_ = 0;
    int row_size_ = 0, col_size_ = 0;
};


/*
现在给定一组确诊人员编号 (X1, X2, X3, ..., n)，在所有人当中，找出哪些人需要进行核酸检测，
输出需要进行核酸检测的人数。(注意：确诊病例自身不需要再做核酸检测)
需要进行核酸检测的人，是病毒传播链条上的所有人员，即有可能通过确诊病例所能传播到的所有人

输入描述
第一行为总人数N
第二行为确诊病例人员编号(确诊病例人员数量<N)，用逗号分割
第三行开始，为一个N*N的矩阵，表示每个人员之间是否有接触，0表示没有接触，1表示有接触。

输出描述
整数：需要做核酸检测的人数
人员编号从0开始

输入
5
1,2
1,1,0,1,0
1,1,0,0,0
0,0,1,0,1
1,0,0,1,0
0,0,1,0,1
输出
3
 */
class Solution03
{
public:
    Solution03(int total, vector<int>&start_v, vector<vector<int>>&grid)
    {
        vector<bool>checked(total, false);
        deque<int>bfs_queue;
        for (auto&index:start_v)
        {
            bfs_queue.push_back(index);
            //标为已访问
            checked[index] = true;
        }

        while (!bfs_queue.empty())
        {
            int top_i = bfs_queue.front();
            bfs_queue.pop_front();
            result++;

            vector<int>top_v = grid[top_i];
            int size = top_v.size();
            for (int next=0; next< size; next++)
            {
                //不相等，未访问，符合要求
                if (next == top_i) continue;
                bool is_visited = checked[next];
                bool is_available = top_v[next] == 1;

                if (!is_visited && is_available)
                {
                    bfs_queue.push_back(next);
                    //标为已访问
                    checked[next] = true;
                    //for---
                }

                //for---
            }

            //while---
        }
        

        int start_v_size = start_v.size();
        cout << result - start_v_size;
	    //Solution03
    }
private:
    int result = 0;
};


/*
输入N个互不相同的二维整数坐标，求这N个坐标可以构成的正方形数量

输入描述
第一行输入为N，N代表坐标数量，N为正整数。N <= 100
之后的 N 行输入为坐标x y以空格分隔，x，y为整数，-10 <= x, y <= 10

输出描述
输出可以构成的正方形数量

输入
4
0 0
1 2
3 1
2 -1
输出
1
 */
class Solution04
{
public:
    string getPosStr(vector<double>&pos_item)
    {
        if (pos_item.size() < 2) return "";
        string pos_str;
        pos_str += to_string(pos_item[0]);
        pos_str += ',';
        pos_str += to_string(pos_item[1]);

        return pos_str;
	    //getPosStr
    }

    Solution04(vector<vector<double>>&pos_vec)
    {
        //先把所有的点存到set中
        //两两组合，计算另外2个点，如果另外两个点在set中
        //直接往set里推这两个点，最后结果，set的长度
        unordered_set<string>total_set;
        for (auto&pos_item:pos_vec)
        {
            string pos_str = getPosStr(pos_item);
            total_set.insert(pos_str);
        }

        unordered_set<string>square_line;

        int v_size = pos_vec.size();
        for (int i=0;i< v_size; i++)
        {
            double x_1 = pos_vec[i][0];
            double y_1 = pos_vec[i][1];
            vector<double>pos_v_1 = { x_1, y_1 };
            string pos_1 = getPosStr(pos_v_1);
            
            for (int next=i+1; next<v_size; next++)
            {
                double x_2 = pos_vec[next][0];
                double y_2 = pos_vec[next][1];
                vector<double>pos_v_2 = { x_2, y_2 };
                string pos_2 = getPosStr(pos_v_2);

                //a+b=x_2-x_1 a-b=y_2-y_1
            	//a=((x_2-x_1)+(y_2-y_1))/2
				//b=((x_2-x_1)-(y_2-y_1))/2
                double a = ((x_2 - x_1) + (y_2 - y_1)) / 2;
                double b = ((x_2 - x_1) - (y_2 - y_1)) / 2;

                double x_3 = x_1 + b;
                double y_3 = y_1 + a;
                vector<double>pos_3_v = { x_3, y_3 };
                string pos_3 = getPosStr(pos_3_v);

                double x_4 = x_1 + a;
                double y_4 = y_1 - b;
                vector<double>pos_4_v = { x_4, y_4 };
                string pos_4 = getPosStr(pos_4_v);

                if (total_set.count(pos_3)>0 && total_set.count(pos_4)>0)
                {
                    string combine = pos_1;
                    combine += ' ';
                    combine += pos_2;
                    square_line.insert(combine);
                }
                

                //for---
            }
            //for---
        }

        int line_size = square_line.size();
        cout << line_size / 2;
	    //Solution04
    }
};


/*
 幼儿园里有一个放倒的圆桶，它是一个线性结构，允许在桶的右边将篮球放入，
 可以在桶的左边和右边将篮球取出
 每个篮球有单独的编号，老师可以连续放入一个或多个篮球，小朋友可以在桶左边或右边将篮球取出，
 当桶里只有一个篮球的情况下，必须从左边取出
如老师按顺序放入1、2、3、4、5 共5个编号的篮球，
那么小朋友可以依次取出的编号为1、2、3、4、5或者3、1、2、4、5编号的篮球，
无法取出5、1、3、2、4编号的篮球
其中3、1、2、4、5的取出场景为:
连续放入1、2、3号 -> 从右边取出3号 -> 从左边取出1号 -> 从左边取出2号 -> 放入4号 -> 从左边取出4号 -> 放入5号>从左边取出5号
简单起见，我们以L表示左，R表示右，此时的篮球的依次取出序列为"RLLLL"

输入描述
每次输入包含一个测试用例:
1、第一行的数字作为老师依次放入的篮球编号
2、第二行的数字作为要检查是否能够按照放入顺序取出的篮球编号

输出描述
对于每个篮球的取出序列，如果确实可以获取，请打印出其按照左右方向的操作的取出顺序
如果无法获取则打印"NO"

输入
4,5,6,7,0,1,2
6,4,0,1,2,5,7
输出
RLRRRLL
 */
class Solution05
{
public:
    Solution05(vector<int>&push_v, vector<int>&search_v)
    {
        string result;
        int index = 0;//待寻找

        deque<int>exec_queue;

        int v_size = push_v.size();
        for (int i=0; i<v_size; i++)
        {
            //允许右边放入
            exec_queue.push_back(push_v[i]);

            while (!exec_queue.empty() && index<v_size)
            {
                bool is_find = false;
                if (exec_queue.front() == search_v[index])
                {
                    exec_queue.pop_front();
                    result += 'L';
                    index++;
                    is_find = true;
                }

                if (index<v_size&&exec_queue.back() == search_v[index])
                {
                    if (exec_queue.size()==1)
                    {
                        //只有一个篮球的情况下，必须从左边取出
                        result += 'L';
                    }
                    else
                    {
                        result += 'R';
                    }
                    exec_queue.pop_back();
                    index++;
                    is_find = true;
                }
                if (!is_find) break;
                //while
            }
        }

        if (!exec_queue.empty())
        {
            cout << "NO";
            return;
        }
        cout << result;
	    //Solution05
    }
};


int main()
{
	{
        string push_str;
        getline(cin, push_str);
        stringstream push_sstream(push_str);
        string token;
        vector<int>push_v;
        while (getline(push_sstream, token, ','))
        {
            push_v.push_back(stoi(token));
        }

        string search_str;
        getline(cin, search_str);
        stringstream search_sstream(search_str);
        vector<int>search_v;
        while (getline(search_sstream,token, ','))
        {
            search_v.push_back(stoi(token));
        }
        Solution05 solu(push_v, search_v);

        return 0;
	}
	{
        int v_size;
        cin >> v_size;
        vector<vector<double>>pos_vec(v_size);

        for (int i=0; i<v_size; i++)
        {
            vector<double>item_v(2);
            cin >> item_v[0] >> item_v[1];
            pos_vec[i] = item_v;
        }
        Solution04 solu(pos_vec);

        return 0;
	}
	{
        string total_str;
        getline(cin, total_str);
        int total = stoi(total_str);

        vector<int>start_v;
        string start_str;
        getline(cin, start_str);
        stringstream start_sstream(start_str);
        string token;
        while (getline(start_sstream, token, ','))
        {
            start_v.push_back(stoi(token));
        }

        vector<vector<int>>grid(total);
        for (int i=0; i<total; i++)
        {
            vector<int>item_v;
            string item_str;
            getline(cin, item_str);
            stringstream item_sstream(item_str);
            while (getline(item_sstream, token, ','))
            {
                item_v.push_back(stoi(token));
            }
            grid[i] = item_v;
        }

        Solution03 solu(total, start_v, grid);

        return 0;
	}
	{
        int total, row_size;
        cin >> total >> row_size;

        //int total=9, row_size=3;
        
        Solution02 solu(total, row_size);

        return 0;
	}
/*
5,4,2,3,2,4,9
10
*/
    vector<int>num_vec;
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    while (getline(oh_sstream,token,','))
    {
        num_vec.push_back(stoi(token));
    }
    int total;
    cin >> total;
    Solution01 solu(num_vec, total);


}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
